package data_structure;

import java.util.LinkedList;
import java.util.List;

public class leetcode_1382 {
    public TreeNode balanceBST(TreeNode root) {
        List<Integer> list=new LinkedList<>();
        trans(list,root);
        TreeNode node = new TreeNode();
        tran(list,node,0,list.size()-1);
        return node;
    }
    public void trans(List<Integer> list,TreeNode node){
        if(node==null) return;
        trans(list,node.left);
        list.add(node.val);
        trans(list,node.right);
    }
    public void tran(List<Integer> list,TreeNode node,int left,int right){
        if(left>right) return;
        int mid=left+(right-left)/2;
        node.val=list.get(mid);
        if(left<=mid-1) node.left=new TreeNode();
        tran(list,node.left,left,mid-1);
        if(right>=mid+1) node.right=new TreeNode();
        tran(list,node.right,mid+1,right);
    }
}
